package com.hardy.leetcode;

/**
 * User: Ruijie Date: 2016/8/25
 */
public class SurroundedRegions {
    public static void solve1(char[][] board){
        if(board==null||board.length==0){
            return;
        }
        int row=board.length,col=board[0].length;
        for(int i=0;i<row;i++){
            //遍历最左边的一列
            dfs(i,0,row,col,board);
            //遍历最右边的一列
            dfs(i,col-1,row,col,board);
        }
        for(int j=1;j<col-1;j++){
            //遍历最上面的一行
            dfs(0,j,row,col,board);
            //遍历最下面的一行
            dfs(row-1,j,row,col,board);
        }
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(board[i][j]=='O'){
                    board[i][j]='X';
                }else if(board[i][j]=='#'){
                    board[i][j]='O';
                }
            }
        }
    }

    private static void dfs(int i, int j, int row, int col, char[][] board) {
        if(i<0||i>=row||j<0||j>=col||board[i][j]!='O'){
            return;
        }
        board[i][j]='#';
        dfs(i-1,j,row,col,board);
        dfs(i+1,j,row,col,board);
        dfs(i,j-1,row,col,board);
        dfs(i,j+1,row,col,board);
    }

    public static void solve(char[][] board){
        int row=board.length;
        if(row==0){
            return;
        }
        int col=board[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(board[i][j]=='O'){
                    int left=j-1,right=j+1,top=i-1,bleow=i+1;
                    boolean flag=false;
                    for(;left>=0;left--){
                        if(board[i][left]=='X'){
                            break;
                        }else{
                            if(!isSetX(i,left,row,col,board)){
                                flag=true;
                                break;
                            }
                        }
                    }
                    //探测右边
                    for(;right<col;right++){
                        if(board[i][right]=='X'){
                            break;
                        }else{
                            if(!isSetX(i,right,row,col,board)){
                                flag=true;
                                break;
                            }
                        }
                    }
                    //探测上边
                    for(;top>=0;top--){
                        if(board[top][j]=='X'){
                            break;
                        }else{
                            if(!isSetX(top,j,row,col,board)){
                                flag=true;
                                break;
                            }
                        }
                    }
                    //探测下边
                    for(;bleow<row;bleow++){
                        if(board[bleow][j]=='X'){
                            break;
                        }else{
                            if(!isSetX(bleow,j,row,col,board)){
                                flag=true;
                                break;
                            }
                        }
                    }
                    if((left==0&&board[i][left]=='X')||left>0){
                        if((right==col-1 && board[i][right]=='X')||right<col){
                            if((top==0&&board[top][j]=='X')||top>0){
                                if((bleow==row-1&&board[bleow][j]=='X')||bleow<row){
                                    if(!flag){
                                        board[i][j]='X';
                                    }
                                }
                            }
                        }
                    }

                }
            }
        }
    }

    private static boolean isSetX(int i, int j, int row, int col, char[][] board) {
        if(i<0||i>=row||j<0||j>=col){
            return false;
        }
        int left=j,right=j,top=i,bleow=i;
        //探测左边
        for(;left>=0;){
            if(board[i][left]=='X'){
                break;
            }
        }
        //探测右边
        for(;right<col;right++){
            if(board[i][right]=='X'){
                break;
            }
        }
        //探测上边
        for(;top>=0;top--){
            if(board[top][j]=='X'){
                break;
            }
        }
        //探测下边
        for(;bleow<row;bleow++){
            if(board[bleow][j]=='X'){
                break;
            }
        }
        if((left==0&&board[i][left]=='X')||left>0){
            if((right==col-1 && board[i][right]=='X')||right<col){
                if((top==0&&board[top][j]=='X')||top>0){
                    if((bleow==row-1&&board[bleow][j]=='X')||bleow<row){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        char[][] arg={{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}};
        char[][] arg1={{'O','X','X','O','X'},
                       {'X','O','O','X','O'},
                       {'X','O','X','O','X'},
                       {'O','X','O','O','O'},
                       {'X','X','O','X','O'}};
        char[][] arg2={{'O'}};
        char[][] arg3={{'O','X','O','O','X','X'},
                       {'O','X','X','X','O','X'},
                       {'X','O','O','X','O','O'},
                       {'X','O','X','X','X','X'},
                       {'O','O','X','O','X','X'},
                       {'X','X','O','O','O','O'}};
        char[][] arg4={{'O','X','O','O','X','X'},
                       {'O','X','X','X','O','X'},
                       {'X','O','O','X','O','O'},
                       {'X','O','X','X','X','X'},
                       {'O','O','X','O','X','X'},
                       {'X','X','O','O','O','O'}};
       // solve(arg);
       // printCharArray(arg1);
       // System.out.println();
       // printCharArray(arg3);
       // System.out.println();
        printCharArray(arg4);
       // solve(arg1);
       // solve(arg3);
        solve(arg4);
        //printCharArray(arg);
      //  System.out.println();
       // printCharArray(arg3);
       // System.out.println();
       // printCharArray(arg1);
        System.out.println();
        printCharArray(arg4);
    }
    private static void printCharArray(char[][] arg) {
        for(int i=0;i<arg.length;i++){
            int k=0;
            for(int j=0;j<arg[0].length;j++){
                k++;
                System.out.print(arg[i][j]+" ");
            }
            if(k==arg[0].length){
                System.out.println();
            }

        }
    }
}
